package me.qingy.old.array;

import java.util.Arrays;

/**
 * @author qingy
 * @since 2021/1/24
 */
public class NextPermutation {
    /**
     * 暴力法：
     * 时间复杂度：O(n!)，可能的排列总计有 n! 个。
     * 空间复杂度：O(n)，需要额外数组将用于存储排列，不符合题目要求
     * <p>
     * 一遍扫描：
     * 思路：从后向前找到最小的升序子序列，将升序子序列中的最高位与剩余序列中只比最高位大的数字进行交换
     * 并将剩余序列升序，整个数值即为下一个字典序
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(1)
     */
    public void nextPermutation1(int[] nums) {
        int n = nums.length;

        // 1. 从后向前找到升序子序列，找到第一次下降的数，位置记为k
        // 找到k，就找到了升序子序列中的最高位
        // 为什么是n-2？如果是在for循环中，从后向前即i=n-1，k=i-1（逻辑i）
        int k = n - 2;
        while (k >= 0 && nums[k] >= nums[k + 1])
            k--;

        // 2. 不存在更大排列情况 如果k=-1，说明所有数降序排列，改成升序排列
        // 即题：如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）
        if (k == -1) {
            // 快排 时间复杂度：O(nlogn)
            Arrays.sort(nums);
            return;
        }

        // 3. 一般情况 k >= 0 那么必然存在升序子序列
        // 3.1 依次遍历剩余降序排列的部分，找到要替换最高位的那个，即先去找比他小的数，之后向前推一位即找到了刚好比他大的那个数
//        int j = k + 1; k+1肯定比k大，而要找的是比他小的数
        int j = k + 2;
        while (j < n && nums[j] > nums[k])
            j++;

        // 3.2 交换j-1和k位置上的数
        // 当前的j，就是剩余降序排列部分第一个比nums[k]小的数，j-1则为替换最高位的那个数
        swap(nums, k, j);
        int temp;

        // 3.3 将k之后的剩余部分变成升序排列
        // k之后的剩余部分必为降序序列，头尾两两交换后就为升序
        int start = k + 1;
        int end = n - 1;
        while (start < end) {
            temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

    /**
     * 优化：
     * 1. 我们只需要逆序，使用自己的算法可以达到O(n)时间复杂度，不需要使用预设的快排
     * 2. 方法提取
     */
    public void nextPermutation(int[] nums) {
        int n = nums.length;

        int k = n - 2;
        while (k >= 0 && nums[k] >= nums[k + 1])
            k--;

        if (k == -1) {
            reverse(nums, 0, n - 1);
            return;
        }

        int j = k + 2;
        while (j < n && nums[j] > nums[k])
            j++;

        swap(nums, k, j-1);

        reverse(nums, k + 1, n - 1);
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }

    private void swap(int[] nums, int x, int y) {
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }

    public static void main(String[] args) {

    }
}
